package Graph.graphWithNoweight.bfs;

import Graph.graphWithNoweight.dfs.Graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: 蔡翔
 * @Date: 2020/2/8 11:37
 * @Version 1.0
 */
public class SingleSourcePath {
    private Graph G;
    private boolean[] visited;
    private int source;
    private int[] pre;
    private ArrayList<Integer> order = new ArrayList<>();

    public SingleSourcePath(Graph G,int source){
        this.G = G;
        this.source = source;
        pre = new int[G.V()];
        visited = new boolean[G.V()];

        for(int i=0;i<G.V();i++){
            pre[i] = -1;
        }

        bsf(0);
    }


    public boolean isConncetedTo(int t){
        G.validateVertex(t);
        //如果源点 与t 在一个联通分量里面，那么这两个点一定是联通的。
        return visited[t];
    }

    //参数 t 为目标节点，，返回的是到t 的路径（这里是倒叙）
    public Iterable<Integer> path(int t){
        ArrayList<Integer> res = new ArrayList<>();
        if(!isConncetedTo(t)){
            return res;
        }
        int cur = t;
        //倒叙 ，从后往前找的、
        while (cur != source){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(source);

        Collections.reverse(res);
        return res;
    }

    private void bsf(int s) {
        Queue<Integer> queue = new LinkedList<>();
        visited[s] = true;
        queue.add(s);
        pre[s] = s;
        while (!queue.isEmpty()){
            Integer v = queue.remove();
            order.add(v);
            for(Integer w:G.adj(v)){
                if(!visited[w]){
                    queue.add(w);
                    visited[w] = true;
                    pre[w] = v;
                }
            }
        }
    }

    public Iterable<Integer> order(){
        return order;
    }

    public static void main(String[] args) {
        Graph g = new Graph("g.txt");
        SingleSourcePath graphBFS = new SingleSourcePath(g,0);
        System.out.println(graphBFS.path(6));
    }

}
